package com.gaojiawei.review;

import java.io.PipedReader;
import java.util.PriorityQueue;

public class ReviewCheck {
    public static void main(String[] args) {

    }

    public static int findTarget(int[] arr,int target){
        if(arr == null || arr.length ==0){
            return -1;
        }
        int len = arr.length;
        int left = 0;
        int right = len-1;
        while(left<= right){
            int mid = left +((right-left)>>1);
            if(arr[mid] == target){
                return mid;
            }else if(arr[mid] >target){
                right = mid-1;
            }else {
                left = mid+1;
            }
        }
        return -1;

    }

    public static ListNode reverseK(ListNode head,int k){
        ListNode end = findK(head,k);
        if(end == null){
            return head;
        }
        ListNode start = head;
        head = end;
        reverse(start,end);
        ListNode lastEnd =start;
        while(lastEnd != null){
            start = lastEnd.next;
            end = findK(start,k);
            if(end == null){
                return head;
            }
            reverse(start,end);
            lastEnd = start;
            lastEnd.next = end;
        }



        return head;
    }

    public static void reverse(ListNode start,ListNode end){
         end = end.next;
         ListNode cur = start;
         ListNode pre = null;
         ListNode next = null;
         while (cur != end){
             next = cur.next;
             cur.next = pre;
             pre = cur;
             cur = cur.next;
         }
         start.next = end;

    }

    public static ListNode findK(ListNode start,int k){
        if(start == null){
            return null;
        }
        while (--k > 0 && start != null){
            start = start.next;
        }
        return start;
    }

    public static ListNode merge(ListNode[] lists){
        if(lists== null || lists.length == 0){
            return null;
        }

        PriorityQueue<ListNode> priorityQueue = new PriorityQueue<>((l1,l2)->{
            return l1.val - l2.val;
        });

        for(ListNode node:lists){
            if(node != null){
                priorityQueue.add(node);
            }
        }

        if(priorityQueue.isEmpty()){
            return null;
        }

        ListNode head = priorityQueue.poll();
        if(head.next != null){
            priorityQueue.add(head.next);
        }
        ListNode cur = head;
        while(!priorityQueue.isEmpty()){
            cur.next = priorityQueue.poll();
            cur = cur.next;
            if(cur.next != null){
                priorityQueue.add(cur.next);
            }
        }

        return head;
    }



    public static class ListNode{
        ListNode next;
        int val;

    }
}
